#include <gtest/gtest.h>
#include <string>

// #ifdef __cplusplus  
// extern "C"  {
// #endif  

// #include "common.h"

// #ifdef __cplusplus  
// }  
// #endif  

using namespace ::std;

template <typename T = int>
void printVector(vector<T>& out) {
    // cbegin() 返回 const_iterator，访问时不可以改变元素的值 Container<T>::const_iterator
    for (auto it = out.cbegin(); it != out.cend() ; ++it) cout << *it << " "; cout << endl;
}

// KMP算法
class Solution {
public:
    int strStr(string haystack, string needle);
	vector<int> getTransferArray(string substr);
};

int Solution::strStr(string haystack, string needle) {
	if(needle.size() == 0) return 0;
	vector<int> transferArray = getTransferArray(needle);
	int i, j, k;
	for(i = 0; i < haystack.size(); ++i) {
		for(j = i, k = 0; j < haystack.size() && k < needle.size() && -1 != k; ) {
			if(haystack[j] == needle[k]) {
				++j; ++k;
			} else {
				if(0 == k) break;
                i = i + k - (transferArray[k - 1] + 1);
				k = transferArray[k - 1] + 1;
			}
		}		
		if(k == needle.size()) {
			cout << "i = " << i << ", j = " << j <<", k = " << k << endl;
			return j - k;
		}
	}
	cout << -1 << endl;
	return -1;
}

vector<int> Solution::getTransferArray(string substr) { // 辅助转移的数组
	int size = substr.size();
	vector<int> transferArray(size, -1);
	for(int i = 1; i < size; ++i) {
		for(int j = i - 1; j >= 0; ) {
			j = transferArray[j];
			if(substr[j + 1] == substr[i]) {
				transferArray[i] = j + 1;
				break;
			}
		}
	}
	printVector(transferArray);
	return transferArray;
}

// 暴力求解辅助转移数组
// vector<int> getTransferArray(string substr) {
// 	int size = substr.size();
// 	vector<int> transferArray(size, -1);
// 	for(int i = 1; i < size; ++i) {
// 		for(int j = i, k = i - 1; k >= 0; --k) {
// 			int m = j, n = k;
// 			while(n >= 0 && substr[m] == substr[n]) {
// 				--m; --n;
// 			}
// 			if(n < 0) {
// 				transferArray[i] = k;
// 				break;
// 			}
// 		}
// 	}
// 	::printVector(transferArray);
// 	return transferArray;
// }

// 根据先前求解的结论，加速后续的求解
vector<int> getTransferArray(string substr) {
	int size = substr.size();
	vector<int> transferArray(size, -1);
	for(int i = 1; i < size; ++i) {
		for(int j = i - 1; j >= 0; ) {
			j = transferArray[j];
			if(substr[j + 1] == substr[i]) {
				transferArray[i] = j + 1;
				break;
			}
		}
	}
	printVector<int>(transferArray);
	return transferArray;
}

// class Solution {
// public:
//     int strStr(string haystack, string needle) {
//         int n = haystack.size(), m = needle.size();
//         if (m == 0) {
//             return 0;
//         }
//         vector<int> pi(m);
//         for (int i = 1, j = 0; i < m; i++) {
//             while (j > 0 && needle[i] != needle[j]) {
//                 j = pi[j - 1];
//             }
//             if (needle[i] == needle[j]) {
//                 j++;
//             }
//             pi[i] = j;
//         }

//         for (int i = 0, j = 0; i < n; i++) {
//             while (j > 0 && haystack[i] != needle[j]) {
//                 j = pi[j - 1];
//             }
//             if (haystack[i] == needle[j]) {
//                 j++;
//             }
//             if (j == m) {
//                 return i - m + 1;
//             }
//         }
//         return -1;
//     }
// };

// void getMaxPrefix(string needle) {
// 	int m = needle.size();
// 	vector<int> pi(m);
// 	for (int i = 1, j = 0; i < m; i++) {
// 		while (j > 0 && needle[i] != needle[j]) {
// 			j = pi[j - 1];
// 		}
// 		if (needle[i] == needle[j]) {
// 			j++;
// 		}
// 		pi[i] = j;
// 	}
// 	printVector(pi);
// }

class StrStrCheck : public ::testing::Test {
public:
	class Solution solution;
};

// TEST_F(StrStrCheck, testGetTransferArray) {
// 	string needle = "aaaaab";
// 	vector<int> out = getTransferArray(needle);
// 	getTransferArray("abababa");
// 	getTransferArray("hello");
// 	getTransferArray("aabaaab");
// 	getMaxPrefix("aabaaab");
// }

TEST_F(StrStrCheck, testStrStr_1) {
	string haystack = "hello", needle = "ll";
	EXPECT_TRUE(2 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_2) {
	string haystack = "aaaaa", needle = "bba";
	EXPECT_TRUE(-1 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_3) {
	string haystack = "hellofaslkdjdddssssalkfjiefjksldghwiofljsddddwordddddldddsaalkjfsd", needle = "dddwordddddld";
	EXPECT_TRUE(42 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_4) {
	string haystack = "", needle = "";
	EXPECT_TRUE(0 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_5) {
	string haystack = "aabaaabaaac", needle = "aabaaac";
	EXPECT_TRUE(4 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_6) {
	string haystack = "ababbbbaaabbbaaa", needle = "bbbb";
	EXPECT_TRUE(3 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_7) {
	string haystack = "mississippi", needle = "pi";
	EXPECT_TRUE(9 == solution.strStr(haystack, needle));
}

TEST_F(StrStrCheck, testStrStr_8) {
	string haystack = "aberrddfdcd", needle = "cd";
	EXPECT_TRUE(9 == solution.strStr(haystack, needle));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
